package middle.code01_window_preprocess;

import lombok.extern.slf4j.Slf4j;

/**
 * 问题：给定一个有序数组arr，代表数轴上从左到右有n个点arr[0]、arr[1]...arr[n-1]。
 * 给定一个正数L，代表一根长度为L的绳子，求绳子最多能覆盖其中的几个点。
 */
@Slf4j
public class Code01_MaxSpots {

    /**
     * 思路一
     * 从左到右，当来到数组i位置的时候，计算arr[i]-L的值，二分查找数组0~i之间大于等于arr[i]-L的值，i的减去这个值的下标再加1就是i位置左侧能够包含最多的点，遍历数组并找到最大的就是要求的值。
     * O(N logN)
     *
     * @param arr
     * @param L
     * @return
     */
    private static int maxSpots1(int[] arr, int L) {
        int max = 0;
        for (int end = 0; end < arr.length; end++) {
            int start = arr[end] - L;
            // 大于等于 start 的最小值索引
            int greaterMinIndex = greaterMinIndex(arr, start);
            max = Math.max(max, end + 1 - greaterMinIndex);
        }
        return max;
    }

    private static int greaterMinIndex(int[] arr, int start) {
        int l = 0;
        int r = arr.length - 1;
        int res = -1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] >= start) {
                res = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return res;
    }

    /**
     * 窗口，L与R之间不能超过绳子的长度，初始时L与R都在0位置，num记录覆盖的点的个数，初始时为1，max记录目前覆盖最多的点，初始值为0。
     * R尝试往右移动，此时开始计算L与R+1之间的距离(即L与R+1各自在数组中对应的值的差)有没有超过绳子的长度以及R移动后会不会越界，如果没超过且不越界则num++，R往右移动一位。
     * 继续判断L与R+1之间的距离有没有超过绳子的长度且越不越界，没有R就继续往右移动，直到超过绳子的长度或越界，R和num不变，max与num比较并更新，L往右移动一次，num-1。
     * 重复前面的过程，直到L移动到数组最后的位置，最后返回max
     *
     * @param arr
     * @param L
     * @return
     */
    private static int maxSpots2(int[] arr, final int L) {
        int max = 0;
        int start = 0;
        int end = 0;
        while (start < arr.length) {
            while (end < arr.length && arr[end] - arr[start] <= L) {
                max = Math.max(max, end - start + 1);
                end++;
            }
            start++;
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int L = 3;
        log.info("max spots is {}", maxSpots1(arr, L));
        log.info("max spots is {}", maxSpots2(arr, L));
    }
}
